package main

// 46. 全排列
func main() {
	nums := []int{1, 2, 3}
	permuteNums := permute(nums)

	for _, permuteNum := range permuteNums {
		for _, num := range permuteNum {
			print(num, ",")
		}
		println()
	}
}

func permute(nums []int) [][]int {
	// 回溯， 交换位置
	l := len(nums)
	var res [][]int
	var backtrack func(first int)
	backtrack = func(first int) {
		if first == l {
			res = append(res, append([]int{}, nums...))
			return
		}
		for i := first; i < l; i++ {
			nums[i], nums[first] = nums[first], nums[i]
			backtrack(first + 1)
			nums[i], nums[first] = nums[first], nums[i]
		}
	}

	backtrack(0)
	return res
}

func permuteOld(nums []int) [][]int {
	// 递归
	var res [][]int
	if len(nums) == 0 {
		return res
	}
	if len(nums) == 1 {
		return append(res, nums)
	}
	currVal := nums[0]
	subPermutes := permute(nums[1:])

	for _, subArray := range subPermutes {
		for i := 0; i < len(subArray)+1; i++ {
			prefix := make([]int, i)
			copy(prefix, subArray[:i])
			suffix := make([]int, len(subArray)-i)
			copy(suffix, subArray[i:])
			res = append(res, append(append(prefix, currVal), suffix...))
		}
	}

	return res
}

/**
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：
输入：nums = [1]
输出：[[1]]

提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
**/
